package kyssion.leetcode.num1_50;

public class code33_搜索旋转排序数组 {

    public static void main(String[] args) {
        System.out.println(new code33_搜索旋转排序数组().search(new int[]{
                4,5,6,7,0,1,2
        },5));
    }

    /**
     * 这一道题目其实很简单的
     * 其实就是一种策略,知道了截断点和重点的位置关系,分别执行不同的策略就能解决这个问题了
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        if(nums.length==0){
            return -1;
        }
        return find(nums,0,nums.length-1,target);
    }

    public int find(int[] nums, int left, int right, int target) {
        int midle = (left + right) / 2;
        if (nums[midle] == target) {
            return midle;
        }
        if (left > right) {
            return -1;
        }
        if (nums[midle] < target) {
            if (nums[midle] < nums[right]) {//截断线在中点的左侧
                int a = find(nums, midle + 1, right, target);
                if (a == -1) {
                    a = find(nums, left, midle - 1, target);
                }
                return a;
            } else {//截断线在中点的右侧
                return find(nums, midle + 1, right, target);
            }
        } else {
            if (nums[midle] < nums[right]) {//截断线在中点的左侧
                return find(nums, left, midle - 1, target);
            } else {//截断线在中点的右侧
                int a = find(nums, left, midle - 1, target);
                if (a == -1) {
                    a = find(nums, midle + 1, right, target);
                }
                return a;
            }
        }
    }
}

